`
https://leetcode.cn/problems/satisfiability-of-equality-equations/
`

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function (equations) {
  const uf = new UF(26)
  const noEqual = []
  // 把所有的相等关系联通
  for (const e of equations) {
    // 如果遇到不相等
    if (e[1] === '!') {
      noEqual.push(e)
      continue
    }
    const c1 = e.charCodeAt(0) - 'a'.charCodeAt(0)
    const c2 = e.charCodeAt(3) - 'a'.charCodeAt(0)
    uf.union(c1, c2)
  }

  // 判断所有的不相等关系是否成立
  for (const e of noEqual) {
    const c1 = e.charCodeAt(0) - 'a'.charCodeAt(0)
    const c2 = e.charCodeAt(3) - 'a'.charCodeAt(0)
    if (uf.connected(c1, c2)) return false
  }

  return true
};

class UF {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
  }

  // 将节点 p 和节点 q 连通
  union(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)

    if (rootP === rootQ) {
      return
    }

    this.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    this._count--
  }

  // 判断节点 p 和节点 q 是否连通
  connected(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  _find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this._find(this.parent[x])
    }
    return this.parent[x]
  }
}